using System.Collections.Generic;
using UnityEngine;


namespace Super
{
	/// <summary>
	/// 平衡二叉树
	/// 相比于搜索二叉树，不存在好坏情况，因为一直维护左右高度相差不超过1	特性
	/// 缺点：插入、删除时频繁的调整结构，
	/// 优点：当结构是一次性构建，多次查找时效果最高
	/// 红黑树查找删除的最优解，但是代码内容很对，各种旋转调整。
	/// 就略过
	/// </summary>
	/// <typeparam name="T"></typeparam>
	public class AVLT<T> : BST<T> where T : IComparable<T>
	{
		public AVLT() { }
		public AVLT(T value)
		{
			Insert(value);
		}
		public AVLT(List<T> values)
		{
			foreach (var item in values)
			{
				Insert(item);
			}
		}
		/// <summary>
		/// 插入值，新增节点
		/// 保证左节点值小于根节点，根节点值小于右节点
		/// 维持左右高度相差不超过1						
		/// 假设平衡破坏点是A，A的子树是B		LL
		/// LL___A右旋   RR___A左旋				A	   A右旋			B
		/// LR___B左旋__A右旋				B			-->		C		A
		/// RL___B右旋__A左旋			c		D					D
		/// </summary>
		/// <param name="value"></param>
		public override void Insert(T value)
		{
			root = Insert(root, value);
		}

		private BinaryTreeNode<T> Insert(BinaryTreeNode<T> node, T value)
		{
			if (node == null)
			{
				BinaryTreeNode<T> newNode = new BinaryTreeNode<T>(value);
				newNode.height = 1;
				return newNode;
			}

			if (node.value.CompareTo(value) == 1)
			{
				node.left = Insert(node.left, value);
			}
			else
			{
				node.right = Insert(node.right, value);
			}


			node.height = Mathf.Max(Height(node.left), Height(node.right)) + 1;

			int balanceFactor = BalanceFactor(node);

			if (balanceFactor > 1)
			{
				if (node.left.value.CompareTo(value) == 1)
				{
					return RightRotate(node);
				}
				else
				{
					node.left = LeftRotate(node.left);
					return RightRotate(node);
				}
			}

			if (balanceFactor < -1)
			{
				if (node.right.value.CompareTo(value) == -1)
				{
					return LeftRotate(node);
				}
				else
				{
					node.right = RightRotate(node.right);
					return LeftRotate(node);
				}
			}

			return node;
		}

		/// <summary>
		/// 
		/// </summary>
		/// <param name="value"></param>
		public override void Delete(T value)
		{
			root = Delete(root, value);
		}

		protected override BinaryTreeNode<T> Delete(BinaryTreeNode<T> node, T value)
		{
			if (node == null)
			{
				return null;
			}

			if (node.value.CompareTo(value) == 1)
			{
				node.left = Delete(node.left, value);
			}
			else if (node.value.CompareTo(value) == -1)
			{
				node.right = Delete(node.right, value);
			}
			else
			{
				if (node.left == null && node.right == null)
				{
					return null;
				}
				else if (node.left == null)
				{
					return node.right;
				}
				else if (node.right == null)
				{
					return node.left;
				}
				else
				{
					BinaryTreeNode<T> minNode = FindMin(node.right);
					node.value = minNode.value;
					node.right = Delete(node.right, minNode.value);
				}
			}

			node.height = Mathf.Max(Height(node.left), Height(node.right)) + 1;

			int balanceFactor = BalanceFactor(node);

			if (balanceFactor > 1)
			{
				if (BalanceFactor(node.left) >= 0)
				{
					return RightRotate(node);
				}
				else
				{
					node.left = LeftRotate(node.left);
					return RightRotate(node);
				}
			}

			if (balanceFactor < -1)
			{
				if (BalanceFactor(node.right) <= 0)
				{
					return LeftRotate(node);
				}
				else
				{
					node.right = RightRotate(node.right);
					return LeftRotate(node);
				}
			}

			return node;
		}

		private BinaryTreeNode<T> RightRotate(BinaryTreeNode<T> node)
		{
			BinaryTreeNode<T> newRoot = node.left;
			node.left = newRoot.right;
			newRoot.right = node;

			node.height = 1 + Mathf.Max(Height(node.left), Height(node.right));
			newRoot.height = 1 + Mathf.Max(Height(newRoot.left), Height(newRoot.right));

			return newRoot;
		}

		private BinaryTreeNode<T> LeftRotate(BinaryTreeNode<T> node)
		{
			BinaryTreeNode<T> newRoot = node.right;
			node.right = newRoot.left;
			newRoot.left = node;

			node.height = 1 + Mathf.Max(Height(node.left), Height(node.right));
			newRoot.height = 1 + Mathf.Max(Height(newRoot.left), Height(newRoot.right));

			return newRoot;
		}

	}

}
